/*
Date:20210517 9:13AM
key:1.函数1，二叉树特定节点的深度计算 2.判断深度相同后，判断是否是兄弟。3。注意有左右节点再判断，没有继续递归。
 */
class Solution {
public:
    //迭代版本
    // void deep(TreeNode* root,int&x,int&dep)
    // {
    //     if(root==nullptr){return;}
    //     if(root->val==x)
    //     {
    //         cout<<dep;
    //         return;
    //     }
    //     else
    //     {
    //         dep++;
    //         deep(root->left,x,dep);
    //         dep--;

    //         dep++;
    //         deep(root->right,x,dep);
    //         dep--;
    //     }
    // }
    
    //递归版本
    int deep1(TreeNode* root,int&x,int&dep)
    {
        if(root==nullptr){return 0;}
        if(root->val==x)
        {
            
            return dep;
        }
        else
        {
            dep++;
            int a=deep1(root->left,x,dep);
            dep--;

            dep++;
            int b=deep1(root->right,x,dep);
            dep--;
            return max(a,b);
        }
    }
    //判断非兄弟
    bool isCousins1(TreeNode* root, int&x, int&y)
    {
        
        if(root==nullptr)
        {
            return 0;
        }
        else
        {
            //cout<<root->val<<" ";
            if((root->left!=nullptr&&root->right!=nullptr)&&((x==root->left->val&&y==root->right->val)||(y==root->left->val&&x==root->right->val)))
            {
                return 1;
            }
            else
            {
                return isCousins1(root->left, x, y)||isCousins1(root->right, x, y);
            }
        }
    }

    bool isCousins(TreeNode* root, int x, int y) 
    {
        int dep=0;
        // cout<<deep1(root,x,dep);
        int dep1=0;
        // cout<<deep1(root,y,dep1);
        if(deep1(root,x,dep)==deep1(root,y,dep1))
        {
            if(isCousins1(root, x, y))
            {
                return 0;
            }
            else
            {
                return 1;
            }
        }
        return 0;
    }
};